/**
 * @param {number} maxTime
 * @param {number[][]} edges
 * @param {number[]} passingFees
 * @return {number}
 */
var minCost = function (maxTime, edges, passingFees) {
    // 定义dp[t][i],t时间到达i城市所需要的最小花费
    let dp = new Array(maxTime + 1).fill(0).map(() => new Array(passingFees.length).fill(Infinity))
    dp[0][0] = passingFees[0]

    for (let i = 1; i <= maxTime; i++) {
        for (let [from, to, cost] of edges) {
            if (cost <= i) {
                if (dp[i - cost][from] !== Infinity) {
                    dp[i][to] = Math.min(dp[i][to], passingFees[to] + dp[i - cost][from])
                }
                // 双向
                if (dp[i - cost][to] !== Infinity) {
                    dp[i][from] = Math.min(dp[i][from], passingFees[from] + dp[i - cost][to])
                }
            }
        }
    }

    let res = Infinity;
    for (let i = 0; i < maxTime + 1; i++) {
        res = Math.min(res, dp[i][passingFees.length - 1])
    }

    return res === Infinity ? -1 : res
};